/*
 * @lc app=leetcode.cn id=767 lang=golang
 * @lcpr version=30119
 *
 * [767] 重构字符串
 */

// @lcpr-template-start
package main

import (
	"container/heap"
	"fmt"
)

func main() {
	fmt.Println(reorganizeString("sfffp"))
	fmt.Println(reorganizeString("aaab"))
}

// @lcpr-template-end
// @lc code=start

type Node struct {
	Val   byte
	Count int
}

type MaxHeap []Node

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i].Count > h[j].Count }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}
func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}
func reorganizeString(s string) string {
	m := make(map[byte]int)
	for i := 0; i < len(s); i++ {
		m[s[i]]++
	}

	pq := &MaxHeap{}

	for k, v := range m {
		*pq = append(*pq, Node{Val: k, Count: v})
	}

	heap.Init(pq)

	max := heap.Pop(pq).(Node)

	if len(s)%2 == 1 {
		if max.Count-1 > len(s)/2 {
			return ""
		}
	} else if max.Count > len(s)/2 {
		return ""
	}

	heap.Push(pq, max)

	res := ""
	for pq.Len() > 1 {
		a := heap.Pop(pq).(Node)
		b := heap.Pop(pq).(Node)
		res += string(a.Val)
		res += string(b.Val)
		a.Count--
		b.Count--
		if a.Count > 0 {
			heap.Push(pq, a)
		}
		if b.Count > 0 {
			heap.Push(pq, b)
		}
	}

	if pq.Len() == 1 {
		res += string(pq.Pop().(Node).Val)
	}

	return res
}

// @lc code=end

/*
// @lcpr case=start
// "aab"\n
// @lcpr case=end

// @lcpr case=start
// "aaab"\n
// @lcpr case=end

*/
